package com.buddy.learn.javasource._lock;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

/**
 * Fork/Join 分而治之的方法对超大数组进行排序，可以充分利用CPU资源
 *
 * @author Buddy
 * @date 2021/5/15
 */
public class MergTest {

    private static int MAX = 100;
    private static int arr[] = new int[MAX];

    // 随机初始化
    static {
        Random random = new Random();
        for (int i = 0; i < MAX; i++) {
            arr[i] = random.nextInt(1000);
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        MyTask myTask = new MyTask(arr);
        ForkJoinTask<int[]> taskResult = forkJoinPool.submit(myTask);
        try {
            int[] res = taskResult.get();
            System.out.println(Arrays.toString(res));
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时=" + (end - start) + " ms");
    }

    private static class MyTask extends RecursiveTask<int[]> {

        private int[] source;

        MyTask(int[] source) {
            this.source = source;
        }

        @Override
        protected int[] compute() {
            int length = source.length;
            if (length > 2) {
                int mid = length / 2;
                // 拆分为两个子任务
                MyTask task1 = new MyTask(Arrays.copyOf(source, mid));
                // 把当前数组的计算任务，提交到任务列表中（递归）
                task1.fork();
                MyTask task2 = new MyTask(Arrays.copyOfRange(source, mid, length));
                task2.fork();
                // 将两个有序数组，合并为一个
                int[] res1 = task1.join();
                int[] res2 = task2.join();
                return joinInts(res1, res2);
            } else {
                // 否则，说明集合中只有一个或者两个元素，可以进行排序
                if (length == 1 || source[0] <= source[1]) {
                    // 如果条件成立，说明数组中只有一个元素或者数组中的元素已经排好序了
                    return source;
                } else {
                    int[] temp = new int[length];
                    temp[0] = source[1];
                    temp[1] = source[0];
                    return temp;
                }
            }
        }

        // 该方法用于合并两个有序集合
        private int[] joinInts(int[] arr1, int[] arr2) {
            int len1 = arr1.length, len2 = arr2.length;
            int i = 0, j = 0, k = 0;
            int[] res = new int[len1 + len2];

            while (i < len1 && j < len2) {
                if (arr1[i] < arr2[j]) {
                    res[k++] = arr1[i++];
                } else {
                    res[k++] = arr2[j++];
                }
            }

            while (i < len1) {
                res[k++] = arr1[i++];
            }
            while (j < len2) {
                res[k++] = arr2[j++];
            }

            return res;
        }
    }
}
